//假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。 
//
// 给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则
//的情况下种入 n 朵花？能则返回 true ，不能则返回 false。 
//
// 
//
// 示例 1： 
//
// 
//输入：flowerbed = [1,0,0,0,1], n = 1
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：flowerbed = [1,0,0,0,1], n = 2
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= flowerbed.length <= 2 * 104 
// flowerbed[i] 为 0 或 1 
// flowerbed 中不存在相邻的两朵花 
// 0 <= n <= flowerbed.length 
// 
// Related Topics 贪心 数组 
// 👍 404 👎 0

package com.cute.leetcode.editor.cn;
public class CanPlaceFlowers {
    public static void main(String[] args) {
        Solution solution = new CanPlaceFlowers().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 不存在相邻的两朵花？我居然没有发现
         * 在我无数个判断条件的制约下，终于跑通了
         * 不要这样做，条件太麻烦了，请看题解
         */
        public boolean myCanPlaceFlowers(int[] flowerbed, int n) {
            if (n == 0) return true;
            int len = flowerbed.length;
            if(len == 1) return n == 1 && flowerbed[0] != 1;
            if (len==2) return n == 1 && flowerbed[0]==0 &&flowerbed[1]==0;

            if (flowerbed[0]==0 && flowerbed[1]==0){
                flowerbed[0]=1;
                n--;
                if (n==0) return true;
            }
            if (flowerbed[len-1]==0&&flowerbed[len-2]==0){
                flowerbed[len-1]=1;
                n--;
                if (n==0) return true;
            }
            for (int i = 1; i < len-1 ; i++) {
                if (flowerbed[i-1] == 0 && flowerbed[i+1]==0 && flowerbed[i]!=1){
                    flowerbed[i] = 1;
                    n--;
                    if (n==0) return true;
                }
            }
            return false;
        }


        /**
         * 跳格子的方法：注意原始数组中不存在两个相邻的1
         * 如果当前格子为1，那么至少在下下个位置才能种花
         * 如果当前格子为0：如果当前已经到达了末尾，可以直接种（因为如果末尾的前一个为1的话会直接跳出循环）
         *  或者下一个格子为0的话也可以种
         *  如果当前格子为0且不满足上述两个条件，则需要向前跳三格才行（跳过下一个1再跳两格）
         */
        public boolean CanPlaceFlowers(int[] flowerbed, int n) {
            int len = flowerbed.length;
            for (int i = 0; i < len && n>0 ;) {
                if (flowerbed[i] ==1){
                    i+=2;
                }else if (i == len-1 || flowerbed[i+1]==0){
                    n--;
                    i+=2;
                }else i+=3;
            }
            return n<=0;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}